# 交通信号(好题)
import heapq
from collections import defaultdict
from leetcode import test_function as tf


def traffic_light_dfs(s, t, edges):
    """
    我的方法, 使用dfs, 超时/通过 = 3/7
    """
    graph = defaultdict(list)
    # edge[0]: 终点
    # edge[1]: 绿灯时间
    # edge[2]: 红灯时间
    # edge[3]: 黄灯时间
    # edge[4]: 正向边/反向边
    for u, v, g, r, y in edges:
        graph[u].append((v, g, r, y, True))  # 正向边 True
        graph[v].append((u, g, r, y, False))  # 反向边 False
    min_time = float('inf')

    def dfs(time: int, path, curr_node: int):
        nonlocal s, t, min_time
        path.add(curr_node)
        if curr_node == t:  # 收集结果
            min_time = min(min_time, time)
            return
        if time >= min_time:
            return

        for target, g, r, y, forward in graph[curr_node]:
            if target in path:  # 如果是此前遍历的节点则跳过
                continue
            cycle = g + r + 2 * y  # 一个循环的时间
            ctime = time % cycle  # 在当前循环的位置
            wait_time = 0  # 需要等待的时间, 下一个节点的时间 = 目前时间(time) + 等待时间(wait) + 路程时间
            if forward:  # 正向边, 考虑绿灯的时间
                if ctime >= g:  # 正好是绿灯, 到下一个节点的时间就是time加上黄灯的时间(cost)
                    wait_time += cycle - ctime
            else:  # 反向边, 考虑红灯的时间
                red_time = g + y  # 红灯开始的时间
                if ctime < red_time:
                    wait_time += red_time - ctime
                elif ctime >= red_time + r:
                    wait_time += red_time - ctime + y
            dfs(time + wait_time + y, path, target)
            path.remove(target)

    dfs(0, set(), s)
    return min_time if min_time != float('inf') else -1


def traffic_light_dijkstra(n, s, t, edges):
    """
    dijkstra算法主要就是处理从某一固定节点到其他各个节点的最短路径问题
    Floyd-Warshall算法主要用来计算每对节点之间的最短路径(生成一个矩阵)
    使用优先队列按时间升序处理结点，确保每次处理当前最短时间的路径。
    对于每条边，根据绿灯或红灯阶段计算等待时间和到达时间。
    通过维护距离数组dist剪枝，避免重复处理更劣路径。
    """
    # 构建邻接表，每个结点存储其可达边（包括正向和反向）
    adj = defaultdict(list)
    for u, v, g, r, y in edges:
        # 正向边：u -> v，在绿灯时出发
        adj[u].append((v, g, r, y, True))
        # 反向边：v -> u，在红灯时出发
        adj[v].append((u, g, r, y, False))

    # 初始化距离数组，dist[i]表示到达结点i的最短时间
    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[s] = 0
    # 优先队列，按时间升序排列
    heap = [(0, s)]  # (current_time, current_node)
    heapq.heapify(heap)

    while heap:
        current_time, u = heapq.heappop(heap)
        if u == t:
            return current_time
        if current_time > dist[u]:
            continue  # 已存在更优路径，跳过

        for edge in adj[u]:
            v, g, r, y, is_forward = edge
            cycle = g + r + 2 * y
            if is_forward:
                # 处理正向边：绿灯允许通行
                rem = current_time % cycle
                if rem < g:
                    departure = current_time  # 绿灯期间可立即出发
                else:
                    # 等待到下一个绿灯周期
                    departure = current_time + (cycle - rem)
                arrival = departure + y
            else:
                # 处理反向边：红灯允许通行
                red_start = g + y  # 红灯开始时间
                red_end = red_start + r  # 红灯结束时间
                rem = current_time % cycle
                if red_start <= rem < red_end:
                    departure = current_time  # 红灯期间可立即出发
                else:
                    # 计算下一个红灯开始时间
                    k = current_time // cycle
                    if rem < red_start:
                        departure = k * cycle + red_start
                    else:
                        departure = (k + 1) * cycle + red_start
                arrival = departure + y

            # 更新到达v的时间
            if arrival < dist[v]:  # arrival 到达节点v的时间
                dist[v] = arrival
                heapq.heappush(heap, (arrival, v))

    return -1 if dist[t] == INF else dist[t]


if __name__ == '__main__':
    # n, m, s, t = map(int, input().split())
    # inp = []
    # for _ in range(m):
    #     inp.append(tuple(map(int, input().split())))  # 起点 终点 绿灯 红灯 黄灯
    edges = []
    with open("../../data/2022_e.in", "r") as file:
        n, m, s, t = map(int, file.readline().split())
        for _ in range(m):
            edges.append(tuple(map(int, file.readline().split())))
    inp = [{"edges": [(1, 2, 1, 2, 6), (4, 2, 1, 1, 5), (1, 3, 1, 1, 1), (3, 4, 1, 99, 1)], "s": 1, "t": 4, "n": 4},
           {"edges": edges, "s": s, "t": t, "n": n},
           ]
    out = [11, 31]
    tf(traffic_light_dfs, inp, out)
    tf(traffic_light_dijkstra, inp, out)
